#include <stdio.h>
#include <stdlib.h>

typedef int E;

typedef struct BTreeNode {
    E element;
    struct BTreeNode * left;
    struct BTreeNode * right;
} * Node;

Node createNode(E element){
    Node node = malloc(sizeof(struct BTreeNode));
    node->left = node->right = NULL;
    node->element = element;
    return node;
}

Node insert(Node root,E element){
    if (root){
        if (root->element > element)
            root->left = insert(root->left,element);
        else if (root->element < element)
            root->right = insert(root->right,element);
    } else {
        root = createNode(element);
    }
    return root;
}

void inOrder(Node root){
    if(root == NULL) return;
    inOrder(root->left);
    printf("%d ", root->element);
    inOrder(root->right);
}

Node find(Node root,E target){
    while (root){
        if (root->element > target)
            root = root->left;
        else if (root -> element < target)
            root = root -> right;
        else return root;
    }
    return NULL;
}

Node findMax(Node root){
    while (root && root->right)
        root = root -> right;
    return root;
}

Node delete(Node root, E target){
    if(root == NULL) return NULL;   //都走到底了还是没有找到要删除的结点，说明没有，直接返回空
    if(root->element > target)   //这里的判断跟之前插入是一样的，继续往后找就完事，直到找到为止
        root->left = delete(root->left, target);
    else if(root->element < target)
        root->right = delete(root->right, target);
    else {   //这种情况就是找到了
        if(root->left && root->right) {   //先处理最麻烦的左右孩子都有的情况
            Node max = findMax(root->left);  //寻找左子树中最大的元素
            root->element = max->element;  //找到后将值替换
            root->left = delete(root->left, root->element);  //替换好后，以同样的方式去删除那个替换上来的结点
        } else {   //其他两种情况可以一起处理，只需要删除这个结点就行，然后将root指定为其中一个孩子，最后返回就完事
            Node tmp = root;
            if(root->right) {   //不是左边就是右边
                root = root->right;
            } else {
                root = root->left;
            }
            free(tmp);   //开删
        }
    }
    return root;   //返回最终的结点
}

int main() {
    Node root = insert(NULL, 18);   //插入后，得到根结点
    insert(root,10);
    insert(root,9);
    insert(root,20);
    insert(root,22);
    insert(root,15);
    insert(root,7);
    insert(root,25);

    inOrder(root);   //用中序遍历查看一下结果
    printf("\n");
    printf("%p\n", find(root,17));
    printf("%p\n",find(root,9));
    delete(root,10);
    inOrder(root);
}